package cn.chenxing.module.analysis.outlierdetect;

import cn.chenxing.domain.outlierdtect.DataNode;
import cn.chenxing.utils.CommonUtil;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @Description 离群点分析--lof算法
 * @Author maogen.ymg
 * @Date 2020/4/16 20:09
 */
public class OutlierDetect {
    /**
     * K
     */
    private static final int INIT_K = 5;

    /**
     * 获取处理LOF后的数据
     * @param allNodes 原始点
     * @param errorValue 误差值
     * @return outlierNodeList
     */
    public List<DataNode> getOutlierNode(List<DataNode> allNodes, double errorValue) {

        // 计算k-邻域和k-距离（先计算每个对象与其他对象的欧几里得距离）
        List<DataNode> outlierNodeList = calKdAndKn(allNodes);
        // 可达距离
        calReachDist(outlierNodeList);
        // 可达密度
        calReachDensity(outlierNodeList);
        // 计算局部离群点因子
        calLof(outlierNodeList, errorValue);
        // 按照LOF降序排序
        outlierNodeList.sort(new LofComparator());

        return outlierNodeList;
    }

    /**
     * 计算每个点的K-距离以及K-邻域
     * @param allNodes 所有点
     * @return List<Node>
     */
    private List<DataNode> calKdAndKn(List<DataNode> allNodes) {
        List<DataNode> kdAndKnList = new ArrayList<>();

        for (int i = 0; i < allNodes.size(); i++) {

            List<DataNode> tempNodeList = new ArrayList<>();
            // 定点（NodeName 维度）
            DataNode nodeA = allNodes.get(i);

            // 找到给定点NodeA与其他点NodeB的距离，并记录在NodeB点的distance
            for (DataNode dataNode : allNodes) {
                DataNode nodeB = new DataNode(dataNode.getNodeId(), dataNode.getDimension());
                // 计算NodeA与NodeB的欧几里得距离(distance)
                nodeB.setDistance(getDist(nodeA, nodeB));
                tempNodeList.add(nodeB);
            }

            // 对所有NodeB点中的欧几里得距离（distance）进行升序排序
            tempNodeList.sort(new DistComparator());

            for (int k = 1; k < INIT_K; k++) {
                // 找到NodeB点的前INIT_K位的距离点，并记录到到NodeA的k-邻域
                nodeA.getKNeighbor().add(tempNodeList.get(k));

                if (k == INIT_K - 1) {
                    // 找到NodeB点的第INIT_K位距离，赋值给NodeA点的kDistance
                    nodeA.setKDistance(tempNodeList.get(k).getDistance());
                }
            }
            kdAndKnList.add(nodeA);
        }

        return kdAndKnList;
    }

    /**
     * 计算给定点A与其他点B之间的欧几里得距离
     * @param nodeA 定点A
     * @param nodeB 定点B
     * @return dist
     */
    private double getDist(DataNode nodeA, DataNode nodeB) {
        double dist = 0.0;
        // n维欧氏空间是一个点集,它的每个点可以表示为(x(1),x(2),...x(n))
        double[] dimA = nodeA.getDimension();
        double[] dimB = nodeB.getDimension();

        if (dimA.length - dimB.length == 0) {
            for (int i = 0; i < dimA.length; i++) {
                // 欧氏距离的公式：d=sqrt(∑(xi1-xi2)^2)
                // xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标
                double temp = Math.pow(dimA[i] - dimB[i], 2);
                dist += temp;
            }
            dist = Math.pow(dist, 0.5);
        }
        return dist;
    }

    /**
     * 计算每个点的可达距离
     * reachDist(p,o)=max{ k-distance(o),d(p,o)}
     * @param outlierNodeList outlierNodeList
     */
    private void calReachDist(List<DataNode> outlierNodeList) {

        for (DataNode node : outlierNodeList) {
            for (DataNode dataNode : node.getKNeighbor()) {
                // dataNode-距离
                double kDist = getKDist(dataNode.getNodeId(), outlierNodeList);

                dataNode.setReachDist(Math.max(kDist, dataNode.getDistance()));
            }
        }
    }

    /**
     * 计算每个点的可达密度
     * @param outlierNodeList outlierNodeList
     */
    private void calReachDensity(List<DataNode> outlierNodeList) {
        for (DataNode node : outlierNodeList) {

            double sum = 0;
            // 可达距离和
            for (DataNode dataNode : node.getKNeighbor()) {
                sum += dataNode.getReachDist();
            }
            if(sum != 0) {
                node.setReachDensity(INIT_K*1.0 / sum);
            }else {
                node.setReachDensity(0);
            }
        }
    }

    /**
     * 计算每个点的局部离群点因子
     * @param outlierNodeList outlierNodeList
     * @param errorValue 误差值
     */
    private void calLof(List<DataNode> outlierNodeList, double errorValue) {

        for (DataNode node : outlierNodeList) {
            double sum = 0.0;
            for (DataNode tempNode : node.getKNeighbor()) {
                // 可达距离
                double rd = getReachDist(tempNode.getNodeId(), outlierNodeList);
                // 可达距离/可达密度 和
                sum += rd / node.getReachDensity();
            }
            double lof = CommonUtil.decimalValue(sum*1.0 /INIT_K, 4);
            node.setLof(lof);
            if(Math.abs(lof - 1.0) > errorValue) {
                node.setIsOutlierNode("是");
            }else {
                node.setIsOutlierNode("否");
            }
        }
    }

    /**
     * 获取某个点的k-距离（kDistance）
     * @param nodeId 点的ID
     * @param nodeList 列表
     * @return kDistance
     */
    private double getKDist(int nodeId, List<DataNode> nodeList) {
        double kDist = 0;
        for (DataNode node : nodeList) {
            if (nodeId == node.getNodeId()) {
                kDist = node.getKDistance();
                break;
            }
        }
        return kDist;

    }

    /**
     * 获取某个点的可达距离
     * @param nodeId 点的名
     * @param nodeList 列表
     * @return ReachDist
     */
    private double getReachDist(int nodeId, List<DataNode> nodeList) {
        double kDis = 0;
        for (DataNode node : nodeList) {
            if (nodeId == node.getNodeId()) {
                kDis = node.getReachDensity();
                break;
            }
        }
        return kDis;

    }

    /**
     * 按距离升序排序
     */
    static class DistComparator implements Comparator<DataNode> {
        @Override
        public int compare(DataNode nodeA, DataNode nodeB) {

            if((nodeA.getDistance() - nodeB.getDistance())<0) {
                return -1;
            } else if((nodeA.getDistance() - nodeB.getDistance())>0) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    /**
     * 按LOF降序排序
     */
    static class LofComparator implements Comparator<DataNode> {
        @Override
        public int compare(DataNode nodeA, DataNode nodeB) {

            if((nodeA.getLof()-nodeB.getLof())<0) {
                return 1;
            } else if((nodeA.getLof()-nodeB.getLof())>0) {
                return -1;
            } else {
                return 0;
            }
        }
    }

}
